package edu.whu.rose.clock.kps.algorithm.banks1;

import java.util.NoSuchElementException;

import edu.whu.rose.clock.kps.graph.GraphMatrix;
import edu.whu.rose.clock.util.priorityqueue.FibonacciHeapPQ;
import edu.whu.rose.clock.util.priorityqueue.UnderflowException;

public class DijkstraIterator implements Comparable<DijkstraIterator> {

	private final GraphMatrix graph;
	private final int source;
	
	private SPVertex[] set;
	private FibonacciHeapPQ<SPVertex> queue;

	public DijkstraIterator(GraphMatrix graph, int source) {
		this.graph = graph;
		this.source = source;
		this.set = new SPVertex[graph.getN()];
		this.queue = new FibonacciHeapPQ<SPVertex>();
		
		for (int i = 1; i < graph.getN() + 1; i++) {
			SPVertex spv = null;
			if (i == source) {
				spv = new SPVertex(i, 0.0D);
			}
			else {
				spv = new SPVertex(i, Double.MAX_VALUE);
			}
			int indexID = queue.enqueue(spv);
			spv.setIndexID(indexID);
			set[i - 1] = spv;
		}
	}
	
	public static void main(String[] args) {
		GraphMatrix spg = new GraphMatrix(10);
		spg.loadEdges("test_edge.txt");
		
		DijkstraIterator di = new DijkstraIterator(spg, 4);
		while (di.hasNext()) {
			SPVertex spv = di.next();
			System.out.println(spv.getID()+ " : " + spv.getDistance());
		}
	}
	
	public boolean hasNext() {
		try {
			return ! (peek() == Double.MAX_VALUE);
		}
		catch (UnderflowException ex) {
			return false;
		}
	}
	
	public SPVertex next() {
		if (queue.isEmpty()) {
			throw new NoSuchElementException();
		}
		SPVertex min = null;
		try {
			min = queue.dequeueMin();
		}
		catch (UnderflowException ex) {
			ex.printStackTrace();
		}
		if (set[min.getID() - 1] == null) {
			System.out.println("Error: found exsiting shortest path");
		}
		set[min.getID() - 1] = null;
		int[] neighbors = graph.genNeighbors(min.getID());
		for (int i = 0; i < neighbors.length; i++) {
			if (set[neighbors[i] - 1] == null) {
				continue;
			}
			SPVertex spv = set[neighbors[i] - 1];
			double dis = min.getDistance() + 1.0D;
			if (dis < spv.getDistance()) {
				spv.setDistance(dis);
				spv.setPredecessor(min.getID());
				relax(spv);
			}
		}
		return min;
	}
	
	private void relax(SPVertex spv) {
		try {
			queue.decreaseKey(spv.getIndexID(), spv);
		}
		catch (UnderflowException ex) {
			ex.printStackTrace();
		}
	}

//	public double getDistance(int id) {
//		return set[id - 1].getDistance();
//	}

	private double peek() throws UnderflowException {
		return queue.findMin().getDistance();
	}

	public int compareTo(DijkstraIterator x) {
		try {
			if (peek() < x.peek()) {
				return -1;
			}
			else if (peek() == x.peek()) {
				return 0;
			}
			else {
				return 1;
			}
		}
		catch (UnderflowException ex) {
			ex.printStackTrace();
			System.exit(1);
			return 0;
		}
	}
	
	public int getSource() {
		return source;
	}

}
